/**
 * Copyright (C), 2018-2018
 * FileName: hanoi  * Author:   lcsos
 * Date:     2018/10/12 21:34
 * Description:
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.qdu.study.arithmetic.first;

import java.util.Scanner;

/**
 * 〈一句话功能简述〉<br>
 *  经典汉诺塔算法
 *如果n=1，则将圆盘从A直接移动到C。
 * 如果n=2，则：
 * 1.将A上的n-1(等于1)个圆盘移到B上；
 * 2.再将A上的一个圆盘移到C上；
 * 3.最后将B上的n-1(等于1)个圆盘移到C上。
 *   如果n=3，则：
 * A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下：
 * (1)将A上的n`-1(等于1)个圆盘移到C上。
 * (2)将A上的一个圆盘移到B。
 * (3)将C上的n`-1(等于1)个圆盘移到B。
 * B. 将A上的一个圆盘移到C。
 * C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，步骤如下：
 * (1)将B上的n`-1(等于1)个圆盘移到A。
 * (2)将B上的一个盘子移到C。
 * (3)将A上的n`-1(等于1)个圆盘移到C。
 *    到此，完成了三个圆盘的移动过程。
 *     从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：
 * 第一步  把A上的n-1个圆盘移到B上；
 * 第二步  把A上的一个圆盘移到C上；
 * 第三步  把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。
 *
 * @author Lcs
 * @create 2018/10/12 
 * @since 1.0.0
 */

public class hanoi {
    private static void move(char x, char y) {
        //%c表示转换字符
        System.out.printf("%c-->%c", x, y);
        System.out.print("\n");
    }

  /**
   * 功能描述: <br>
   * 〈〉
   *  将n个盘子从第一座借助第二座移到第三座
   * @since: 1.0.0
   * @Author:Lcs
   * @Date: 2018/10/12 21:38
   */
    private static void hanoit(int n, char one, char two, char three) {
        //如果只有一个盘子
        if (n == 1) {
            move(one,three);
        } else {
            //将一上的盘子借助三移到二上
            hanoit(n - 1, one, three, two);
            move(one,three);
            //将二上的盘子借助一移到三上
            hanoit(n - 1, two, one, three);
        }
    }

    public static void main(String[] args) {
        int m;
        System.out.println("请输入你要移动的盘子数：");
        Scanner s = new Scanner(System.in);
        m = s.nextInt();
        System.out.println("移动" + m + "个盘子的步骤如下");
        hanoit(m, 'A', 'B', 'C');
    }
}
